package NC26_括号生成;

import java.util.ArrayList;

public class Solution {
    /**
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    ArrayList<String> list = new ArrayList<>();
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        /*
        * n： 表示有 n 对括号
        * 一个 "" 空字符串，要么加一个左括号，要么加一个右括号
        * 当 n 个左右括号都加完了，那就是一个结果出来了
        * 条件一：左括号数量一定要先达到 n，所以就不能再加左括号了，left > n 就错了
        * 条件二：肯定有左才有右，如果右括号先放一定错，所以要保证 left >= right*/
        process(n, 0, 0, "");
        return list;
    }

    private void process(int n, int left, int right, String cur) {
        // 如果左括号数量 > n,或者左括号数量大于右括号，直接 return
        if (left > n || right > left){
            return;
        }
        // 满足条件，放入 list
        if (left == n && right == left){
            list.add(cur);
            return;
        }
        // 要么继续加左括号，要么继续加右括号
        // 加一个左括号，左括号数量 + 1
        process(n, left + 1, right, cur + "(");
        // 加一个右括号，右括号数量 + 1
        process(n, left, right + 1, cur + ")");
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.generateParenthesis(3);
    }
}